-------<br />METRIC 2011 Trimester at Institut Henri Poincaré (Paris, France, Jan-Mar 2011)<br />-------<br />Workshop on Metric embeddings, algorithms and hardness of approximation<br />January 17-21, 2011<br />-------<br />Jan 20, 15:00-16:00<br />Johan Hastad (KTH Stockholm)<br />Approximating Linear Threshold Predicates<br />-------<br />For a k-ary predicate P we have a corresponding constraint satisfaction problem Max-P where each constraint is P applied to a k-tuple of literals and the task is to find values of the variables in order to satisfy the maximal number of constraints.<br />For all interesting predicates P this problem is NP-hard and we study efficient approximation algorithms. We are interested in the case when P is a linear threshold predicate, the simplest example being majority of an odd number of variables.<br />In the case of majority we get an almost tight approximation ratio as a function of k and the results extend to predicates which are defined by linear forms with small integral weights.<br />An interesting question left open is whether there are linear threshold predicates that are "approximation resistant", which is defined by the property that no efficient approximation algorithm can achieve a approximation ratio that is better than the ratio obtained by simply picking an assignment at random.<br />This is joint work with Mahdi Cheraghchi, Marcus Isaksson and Ola Svensson
